/**
 * 题目描述：根据一棵树的前序遍历与中序遍历构造二叉树。
 * 注意: 你可以假设树中没有重复的元素。
 * 
 * 前序遍历 preorder = [3,9,20,15,7]
    中序遍历 inorder = [9,3,15,20,7],返回如下的二叉树
    3
   / \
  9  20
    /  \
   15   7
 */

/**
 * 思路分析：在中序序列中定位到根节点对应的坐标，然后基于这个坐标划分出左右子树对应的两个子序列，进而明确左右子树各自在前序、中序遍历序列中对应的索引区间，由此构造左右子树
 * 二叉树题目中的重复逻辑，90%都是通过递归来完成的
 */
 function TreeNode(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
const buildTree = function (preorder, inorder) {
  // 缓存结点总个数（遍历序列的长度）
  const len = preorder.length;
  // 定义构造二叉树结点的递归函数
  function build(preL, preR, inL, inR) {
    // 处理越界情况
    if (preL > preR) {
      return null;
    }
    // 初始化目标结点
    const root = new TreeNode();
    // 目标结点映射的是当前前序遍历序列的头部结点（也就是当前范围的根结点）
    root.val = preorder[preL];
    // 定位到根结点在中序遍历序列中的位置
    const k = inorder.indexOf(root.val);
    // 计算出左子树中结点的个数
    const numLeft = k - inL;
    // 构造左子树
    root.left = build(preL + 1, preL + numLeft, inL, k - 1);
    // 构造右子树
    root.right = build(preL + numLeft + 1, preR, k + 1, inR);
    // 返回当前结点
    return root;
  }
  // 递归构造二叉树
  return build(0, len - 1, 0, len - 1);
};
